package com.sdsmdg.harjot.materialshadows.utilities;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

public class GrahamScan {
    private Deque<Point2D> hull = new ArrayDeque<>();
    private final int NUM_SIZE = 2;
    /**
     * 通过 point2D去计算
     *
     * @param pts point2D
     * */

    public GrahamScan(Point2D[] pts) {
        // defensive copy
        int N = pts.length;
        Point2D[] points = new Point2D[N];
        System.arraycopy(pts, 0, points, 0, N);
        Arrays.sort(points);

        Arrays.sort(points, 1, N, points[0].POLAR_ORDER);

        hull.push(points[0]); // p[0] is first extreme point
        int k1;
        for (k1 = 1; k1 < N; k1++) {
            if (!points[0].equals(points[k1])) {
                break;
            }
        }
        if (N == k1) {
            return; // all points equal
        }
        int k2;
        for (k2 = k1 + 1; k2 < N; k2++) {
            if (Point2D.ccw(points[0], points[k1], points[k2]) != 0) {
                break;
            }
        }
        hull.push(points[k2 - 1]); // points[k2-1] is second extreme point

        for (int i1 = k2; i1 < N; i1++) {
            Point2D top = hull.pop();
            while (Point2D.ccw(hull.peek(), top, points[i1]) <= 0) {
                top = hull.pop();
            }
            hull.push(top);
            hull.push(points[i1]);
        }

        assert isConvex();
    }
    /**
     * 可迭代的
     *
     * @return Point2D
     * */

    public Iterable<Point2D> hull() {
        Stack<Point2D> s1 = new Stack<Point2D>();
        for (Point2D p1 : hull) {
            s1.push(p1);
        }
        return s1;
    }

    private boolean isConvex() {
        int size = hull.size();
        if (size <= NUM_SIZE) {
            return true;
        }

        Point2D[] points = new Point2D[size];
        int n1 = 0;
        for (Point2D pp : hull()) {
            points[n1++] = pp;
        }

        for (int ii = 0; ii < size; ii++) {
            if (Point2D.ccw(points[ii], points[(ii + 1) % size], points[(ii + NUM_SIZE) % size]) <= 0) {
                return false;
            }
        }
        return true;
    }
}
